package q235

import (
	"fmt"
	"math"
	"strconv"
	"strings"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func (root *TreeNode) Print(){
	fmt.Print(root.Sprint())
}

func (root *TreeNode) Sprint()string {
	strArr := []string{root.String()}
	tmp := []*TreeNode{root}

	for {
		tt := []*TreeNode{}
		con := false
		for _, node := range tmp {

			if node != nil {

				tt = append(tt, node.Left)
				tt = append(tt, node.Right)
				if node.Left != nil || node.Right != nil {
					con = true
				}
			} else {
				tt = append(tt, nil)
				tt = append(tt, nil)
			}

		}
		if !con {
			break
		}
		tmp = tt
		for _, node := range tmp {
			strArr = append(strArr, node.String())
		}
	}
	s:=strings.Join(strArr, ",")

	return s
}

//打印字符串
func (node *TreeNode) String() string {
	if node != nil {
		return strconv.Itoa(node.Val)
	}
	return "nil"
}


//比较是否一样
func (node *TreeNode) Compare(compNode *TreeNode) bool {
	if node==nil && compNode==nil{
		return true
	}
	if node.Val!=compNode.Val{
		return false
	}

	if !node.Left.Compare(compNode.Left){
		return false
	}
	if !node.Right.Compare(compNode.Right){
		return false
	}

	return true
}

//创建节点
func MakeTreeNode(val int, left, right *TreeNode) *TreeNode {
	return &TreeNode{Val: val, Left: left, Right: right}
}

//根据数组创建节点
func MakeTreeNodeFromArray(arr []interface{}) *TreeNode {
	level := 0.0
	nodeArr := []*TreeNode{}

	var index = 0
	for i := 0; i < len(arr); {
		if i == 0 {
			var node *TreeNode
			if arr[i] != nil {
				node = MakeTreeNode(arr[i].(int), nil, nil)
			} else {
				node = nil
			}
			nodeArr = append(nodeArr, node)
			i++
			continue
		}
		level++
		levelTotal := math.Pow(2, level-1)

		//log.Printf("----------- %v,levelTotal=%f,i=%d",nodeArr,levelTotal,i)
		//printNode(nodeArr[0]);

		for j := 1.0; j <= levelTotal; j++ {

			var left *TreeNode
			var right *TreeNode
			if arr[i] != nil {
				left = MakeTreeNode(arr[i].(int), nil, nil)
			} else {
				left = nil
			}

			i++
			if arr[i] != nil {
				right = MakeTreeNode(arr[i].(int), nil, nil)
			} else {
				right = nil
			}

			i++

			nodeArr[index].Left = left
			nodeArr[index].Right = right
			index++

			nodeArr = append(nodeArr, left)
			nodeArr = append(nodeArr, right)
		}
	}

	return nodeArr[0]
}
